struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* partition(ListNode* head, int x) {


	ListNode* reshead,*res, * secondRes,*secondHead ,*now;
	res = new ListNode(0);
	secondRes = new ListNode(0);
	reshead = res;
	secondHead = secondRes;
	now = head;
	while (now != nullptr) {
		if (now->val < x)
		{
			res->next = now;
			
			res = res->next;
		}
		else
		{
			secondRes->next = now;
			secondRes = secondRes->next;
		}
		now = now->next;
	}
	secondRes->next = nullptr;
	res->next = secondHead->next;
	delete res;
	delete secondRes;
	return reshead->next;

}
